package com.cqs.leetcode;


import com.cqs.leetcode.ds.ArraysUtils;

import java.util.*;

/**
 * Created by cqs on 2018/3/28.
 */
public class TopKFrequentElements {

    private Map<Integer, Node> map = new HashMap<>();

    private class Node implements Comparable<Node> {
        private int num;
        private int times;

        public Node(int num, int times) {
            this.num = num;
            this.times = times;
        }

        public Node addOne() {
            this.times++;
            return this;
        }


        @Override
        public int compareTo(Node o) {
            return this.times - o.times;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "num=" + num +
                    ", times=" + times +
                    '}';
        }
    }


    public List<Integer> topKFrequent(int[] nums, int k) {
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, new Node(num, 0)).addOne());
        }
        Node[] nodes = new Node[map.values().size()];
        map.values().toArray(nodes);
        List<Integer> topK = new ArrayList<>();
        int length = nodes.length;
        buildHeap(nodes, length);
        while (k-- > 0) {
            topK.add(nodes[0].num);
            nodes[0] = nodes[--length];
            sink(nodes, length, 0);
        }
        return topK;
    }

    //完全二叉树
    private void buildHeap(Node[] nodes, int length) {
        for (int i = length / 2 - 1; i >= 0; --i) {
            sink(nodes, length, i);
        }
    }

    private void sink(Node[] nodes, int length, int index) {
        while (2 * index + 1 < length) {
            int max = 2 * index + 1;
            if (2 * index + 2 < length) {
                Node right = nodes[2 * index + 2];
                if (right.times > nodes[2 * index + 1].times) {
                    max += 1;
                }
            }
            if (nodes[index].times < nodes[max].times) {
                Node tmp = nodes[index];
                nodes[index] = nodes[max];
                nodes[max] = tmp;
            }
            index = max;
        }
    }


    //解法二
    public List<Integer> topKFrequent0(int[] nums, int k) {
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, new Node(num, 0)).addOne());
        }
        System.out.println(map);
        List<Node> list = new ArrayList<>();
        list.addAll(map.values());
        Collections.sort(list);
        List<Integer> sort = new ArrayList<>();
        for (int i = list.size() - 1; i >= list.size() - k; --i) {
            sort.add(list.get(i).num);
        }
        return sort;
    }


    public static void main(String[] args) {
        TopKFrequentElements top = new TopKFrequentElements();
        int[] data = {1, 1, 1, 2, 2, 3};
        data = ArraysUtils.randInts(30);
        Set<Integer> sets = new HashSet<>();
        for (int d : data) {
            sets.add(d);
        }

        ArraysUtils.print(data);
        int k = sets.size();
//        System.out.println(top.topKFrequent0(data, k));
        System.out.println(top.topKFrequent(data, k));
    }

}
